5. Radix Sort.md

date created	date modified	title
Thursday, June 16th 2022, 1:47:45 pm	Sunday, July 24th 2022, 8:40:49 pm	Radix Sort

Radix Sort

• Division and modulo with 10
• Runtime: O( kn)
• Radix sort is a fast distribution sorting algorithm that orders keys by examining the individual components of the keys instead of comparing the keys themselves.

• For example ,
  • When sorting integer keys, the individual digits of the keys are compared from least significant to most significant.
  • This is a special purpose sorting algorithm but can be used to sort many types of keys, including positive integers, strings, and floating-point values.

from collections import deque as Queue


def radixSort(Array):
    numdigit = len(max(Array))

    holder = []
    for i in range(10):
        holder.append(Queue())
    column = 1

    for i in range(numdigit):
        for key in Array:
            place = (key // column) % 10
            holder[place].append(key)

        i = 0
        for bin in holder:
            while bin:
                Array[i] = bin.popleft()
                i += 1

        column *= 10
    print(Array)


def numDigit(Array):
    return str(max(Array))


if __name__ == '__main__':
    radixSort([10, 23, 51, 18, 4, 31, 5, 13])